package me.eg.second;

import java.util.HashMap;
import java.util.Map;

/**
 * 697. 数组的度
 *
 * 链接：https://leetcode-cn.com/problems/degree-of-an-array
 */
public class FindShortestSubArray {
    public int findShortestSubArray(int[] nums) {
        // 哈希、滑动窗口
        // 先计算原数组的度
        Map<Integer, NumDegree> degree = new HashMap<>();

        int maxDegree = 0;
        int minSubArrayLen = 0;
        // 将循环降为一次
        for (int i = 0; i < nums.length; i++) {
            NumDegree numDegree = degree.getOrDefault(nums[i], null);
            if (numDegree == null) {
                numDegree = new NumDegree(1, i);
            } else {
                numDegree.cnt++;
                numDegree.end = i;
            }
            degree.put(nums[i], numDegree);

            if (numDegree.cnt > maxDegree) {
                maxDegree = numDegree.cnt;
                minSubArrayLen = numDegree.end - numDegree.start + 1;
            } else if (numDegree.cnt == maxDegree) {
                if (numDegree.end - numDegree.start + 1 < minSubArrayLen) {
                    minSubArrayLen = numDegree.end - numDegree.start + 1;
                }
            }
        }
        return minSubArrayLen;
    }

    class NumDegree {
        public int cnt;
        public int start;
        public int end;

        public NumDegree(int cnt, int start) {
            this.cnt = cnt;
            this.end = this.start = start;
        }
    }
}
